home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / fractal / kaos.lha / dimslib / dims_qcksort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-01-22  |  2.2 KB  |  114 lines
  1. /* Patrick Worfolk   
  2.    January 22, 1990
  3.    Fractal dimension algorithm functions
  4.    */
  5.  
  6.  
  7. /* DIMS_SORT sorts an array using a quicksort.
  8.   data[x][y] is considered as a list where x indexes the different
  9.   elements and y indexes the different components of one element.
  10.   */
  11.  
  12.  
  13.  
  14. #define M 7
  15. #define NSTACK 50
  16. #define FM 7875
  17. #define FA 211
  18. #define FC 1663
  19. #define TRUE 1
  20. #define FALSE 0
  21.  
  22. void dims_sort(data,xsize,ysize)
  23. int xsize,ysize;
  24. double **data;
  25. {
  26.     int l=1,jstack=0,j,ir,iq,i,k,okay;
  27.     int istack[NSTACK+1];
  28.     long int fx=0L;
  29.     double *temp;
  30.  
  31.     ir=xsize;
  32.     for (;;) {
  33.         if (ir-l < M) {
  34.             for (j=l+1;j<=ir;j++) {
  35.                 temp=data[j-1];
  36.         /* for (i=j-1;data[i-1]>temp && i>0;i--) data[i]=data[i-1]; */
  37.                 i=j-1;
  38.                 okay = TRUE;
  39.                 while (i>0 && okay) {                                    k=0;
  40.                     while ((k<ysize-1) && 
  41.                       (((int) data[i-1][k])==((int) temp[k]))) 
  42.                         k++;
  43.                     if (data[i-1][k]>temp[k]) {
  44.                         data[i]=data[i-1];
  45.                         i--;
  46.                         }
  47.                     else okay=FALSE;
  48.                     }
  49.                 data[i]=temp;
  50.             }
  51.             if (jstack == 0) return;
  52.             ir=istack[jstack--];
  53.             l=istack[jstack--];
  54.         } else {
  55.             i=l;
  56.             j=ir;
  57.             fx=(fx*FA+FC) % FM;
  58.             iq=l+((ir-l+1)*fx)/FM;
  59.             temp=data[iq-1];
  60.             data[iq-1]=data[l-1];
  61.             for (;;) {
  62.                 /* while (j > 0 && temp < data[j-1]) j--;*/
  63.                 okay=TRUE;
  64.                 while (j>0 && okay) {
  65.                     k=0;
  66.                     while ((k<ysize-1) &&
  67.                       (((int) temp[k])==((int) data[j-1][k])))
  68.                         k++;
  69.                     if (temp[k]<data[j-1][k]) j--;
  70.                     else okay=FALSE;
  71.                     }
  72.                 if (j <= i) {
  73.                     data[i-1]=temp;
  74.                     break;
  75.                 }
  76.                 data[-1+i++]=data[j-1];
  77.                 /* while (temp > data[i-1] && i <= xsize) i++;*/
  78.                 okay=TRUE;
  79.                 while (i<=xsize && okay) {
  80.                     k=0;
  81.                     while ((k<ysize-1) &&
  82.                       (((int) temp[k])==((int) data[i-1][k])))
  83.                         k++;
  84.                     if (temp[k]>data[i-1][k]) i++;
  85.                     else okay=FALSE;
  86.                     }
  87.                 if (j <= i) {
  88.                     data[(i=j)-1]=temp;
  89.                     break;
  90.                 }
  91.                 data[--j]=data[i-1];
  92.             }
  93.             if (ir-i >= i-l) {
  94.                 istack[++jstack]=i+1;
  95.                 istack[++jstack]=ir;
  96.                 ir=i-1;
  97.             } else {
  98.                 istack[++jstack]=l;
  99.                 istack[++jstack]=i-1;
  100.                 l=i+1;
  101.             }
  102.             if (jstack > NSTACK) 
  103.               system_mess_proc(1,
  104.                 "(Box algoritm) NSTACK too small in QCKSRT");
  105.         }
  106.     }
  107. }
  108.  
  109. #undef M
  110. #undef NSTACK
  111. #undef FM
  112. #undef FA
  113. #undef FC
  114.